МІНІСТЕРСТВО ОСВІТИ, НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ІСМ
Лабораторна робота №3
на тему:
ПОБУДОВА ФУНКЦІОНАЛЬНИХ ЗАЛЕЖНОСТЕЙ ДЛЯ ОБРАНОЇ ПО
З курсу:
«Теорія систем баз даних та знань»
Мета роботи
Вивчення застосування звичайних булевих операцій над множинами до відношень. Визначення трьох спеціальних операторів над відношеннями: вибору, проекції і з’єднання. Оператори об’єднання, перетину, різниці, активного доповнення, вибірки, натурального зєднання, ділення, перейменування і -з’єднання разом з постійними і регулярниим відношеннями відносяться до реляційної алгебри. Нарешті, аналізуються дві операції, що не належать алгебрі, але іноді корисні при реалізації бази даних, а саме: оператор розщеплення та оператор фактор.
Теоретичні відомості
Функціональна залежність є узагальненням поняттям ключа. Не строго кажучи, F-залежність має місце тоді, коли значення кортежу на одній множині атрибутів єдиним чином визначають ці значення на іншій множині атрибутів.
Нехай r – відношення зі схемою R, X та Y – підмножини. Відношення r задовольняє функціональні залежності X ( Y, якщо має не більше одного кортежу для кожного Х – значення х. Один із способів інтерпретувати ей вираз – розглянути два кортежі та в r. Якщо то . В F-залежності X ( Y підмножина Х називається лівою частиною, відповідно Y – правою.
Алгоритм SATISFIES. Цей алгоритм перевіряє, чи задовольняє відношення r F-залежності X ( Y.
Вхід: відношення r та F-залежність X ( Y. Вихід: істина, якщо r задовольняє X ( Y, хибність – в іншому випадку.
SATISFIES (r, X ( Y);
Відсортуємо відношення за – стовпцями так, щоб зібрати кортеж з рівними – значення разом.
Якщо кожна сукупність кортежів з рівними – значеннями має також рівні – значеннями, то на виході отримуємо істину, в іншому випадку хибність.
Застосування аксіом виведення. Множина функціональних залежностей, що застосовуються до відношення r(R), кінцева, так як існує тільки кінцеве число підмножин множини R. Таким чином, завжди можна знайти всі F – залежності, яким r задовольняє, перебравши всі можливі з допомогою алгоритма SATISFIES. Проте цей підхід потребує більшої кількості часу. Якщо відомі деякі F-залежності з F, тоді здебільшого можна вивести решта. Множина F-залежностей породжує F-залежність X ( Y(позначення: F |( X ( Y), якщо кожне відношення, що задовольняє всім залежностям в F, задовольняє також залежності X ( Y. Аксіома виведення – це правило, яке встановлює, що якщо відношення задовольняє визначеним F – залежностям, тоді воно повинно задовольняти і деяким іншим F – залежностям.
Тепер введемо шість аксіом виведення для F-залежностей. В їх формулюваннях використовуються позначення r для відношення на R і W, X, Y і Z – для підмножин R.
F1. Рефлексивність: X ( X.
F2: Поповнення: X ( Y породжує XZ ( Y.
F3: Адитивність:X ( Y i X ( Z породжує X ( YZ.
F4: Проективність: X ( YZ породжує X ( Y.
F5: Транзитивність: X ( Y i Y ( Z породжує X ( Z.
F6: Псевдотранзитивність: X ( Y i YZ ( W породжує XZ (W.
Аксіоми F1, F2 і F6 складають повну підмножину для F1-F6. Аксіоми F1, F2 i F6також є незалежними: жодна з цих аксіом не може бути отримана з двох інших. Ці три аксіоми називаються іноді аксіомами Армстронга, хоча вони не дуже схожі на вихідну аксіому Армстронга (проте ця назва узвичаєна).
Нехай F – множина F-залежностей для відношення r (R). Замикання F, що позначається, F - це найменша множина, що містить F, така, що при застосуванні до неї аксіом Армстронга не можна одержати жодної F-залежності не приналежної F. Оскільки F повинно бути завжди, то можна обчислити його, починаються з F шляхом застосування F1, F2 і F6 і додавання отриманих Р-залежностей до F доти, поки не перестануть утворюватися нові залежності. Замикання F залежить від схеми R. Якщо R = AB, то F завжди будуть містити B ( B. Коли R не визначене явно, передбачається, що існує множина всіх символів атрибутів, використовуваних у F – залежностях із F.
З множини F можна вивести F-залежність X ( Y, ...
